package com.nc.delivery_project.server.domain.path_finder.old;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by miroshnik on 2/3/2015.
 *
 */

public final class Dijkstra {

    public static <T> Map<T, Double> shortestPaths(DirectedGraph<T> graph, T source) {

        FibonacciHeap<T> pq = new FibonacciHeap<T>();

        Map<T, FibonacciHeap.Entry<T>> entries = new HashMap<T, FibonacciHeap.Entry<T>>();

        Map<T, Double> result = new HashMap<T, Double>();

        for (T node : graph)
            entries.put(node, pq.enqueue(node, Double.POSITIVE_INFINITY));

        pq.decreaseKey(entries.get(source), 0.0);

        while (!pq.isEmpty()) {
            FibonacciHeap.Entry<T> curr = pq.dequeueMin();

            result.put(curr.getValue(), curr.getPriority());

            for (Map.Entry<T, Double> arc : graph.edgesFrom(curr.getValue()).entrySet()) {
                if (result.containsKey(arc.getKey())) continue;

                double pathCost = curr.getPriority() + arc.getValue();

                FibonacciHeap.Entry<T> dest = entries.get(arc.getKey());
                if (pathCost < dest.getPriority())
                    pq.decreaseKey(dest, pathCost);
            }
        }

        return result;
    }

    public static <T> Map<T, Double> shortestPaths(DirectedGraph<T> graph, T source, T target) {

        FibonacciHeap<T> pq = new FibonacciHeap<T>();

        Map<T, FibonacciHeap.Entry<T>> entries = new HashMap<T, FibonacciHeap.Entry<T>>();

        Map<T, Double> result = new HashMap<T, Double>();

        for (T node : graph)
            entries.put(node, pq.enqueue(node, Double.POSITIVE_INFINITY));

        pq.decreaseKey(entries.get(source), 0.0);

        while (!pq.isEmpty()) {
            FibonacciHeap.Entry<T> curr = pq.dequeueMin();

            result.put(curr.getValue(), curr.getPriority());

            for (Map.Entry<T, Double> arc : graph.edgesFrom(curr.getValue()).entrySet()) {
                if (result.containsKey(arc.getKey())) continue;

                double pathCost = curr.getPriority() + arc.getValue();

                FibonacciHeap.Entry<T> dest = entries.get(arc.getKey());
                if (pathCost < dest.getPriority())
                    pq.decreaseKey(dest, pathCost);
            }
        }

        return result;
    }
}